package 搜索算法.深度优先搜索;


import java.util.Stack;

/**
 * 1. 问题描述
 *      给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *      岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *      此外，你可以假设该网格的四条边均被水包围。
 *
 * 2. 算法分析
 *      利用dfs算法实现：主要思路扫描整个二维数组，如果当前为陆地并且没有被访问，就以当前岛屿为起点
 *      找到于该陆地相连的最大连通图，这事就当前找到的最岛屿
 *
 *      由于我们需要判断当前位置的上下左右，但是由于二维数组的边界问题，但我们判断边界的时候会发生数组索引越界
 *      所以我们将初始化一个更大的二维数组，即将原始数组的外部添加上0元素，这样我们就无需考虑索引越界的问题了
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 最大岛屿问题_DFS_递归实现 {
    public static void main(String[] args) {
        int[] pos = new int[] {1,2};
        Stack stack = new Stack();

    }

    /**
     * 采用dfs实现，额外的空间复杂度为 visited数组和扩张的数组area
     * @param grid
     * @return
     */
    public static int numIslands(char[][] grid) {
        int count = 0; // 记录岛屿的数量
        int row = grid.length;
        int col = grid[0].length;
        int[][] area = new int[row+2][col+2];
        // 初始化第一行和最后一行
        for(int j = 0; j < col + 2; j++) {
            area[0][j] = 0;
            area[row+1][j] = 0;
        }
        //  初始化第一列和最后一列
        for(int i = 0; i < row + 2; i++) {
            area[i][0] = 0;
            area[i][col+1] = 0;
        }
        // 初始化中间的位置
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                area[i][j] = grid[i-1][j-1] - 48;
            }
        }
        // 至此我们完成了初始化的工作，下面对aera进行dfs的算法实现
        boolean[][] visited = new boolean[row+2][col+2]; // 默认的初始值为false
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                if(area[i][j] == 1 && visited[i][j] == false) {
                    // 如果当前为陆地，并且没有被访问过
                    dfs(area,visited,i,j);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * dfs算法：深度优先遍历搜索算法
     * @param area：扩张之后的二维数组
     * @param visited：访问数组
     * @param i：当前岛屿的位置
     * @param j：当前岛屿的位置
     */
    public static void dfs(int[][] area, boolean[][] visited, int i, int j) {
        visited[i][j] = true;
        if(area[i-1][j] == 1 && visited[i-1][j] == false) {
            // 判断当前节点的上方
            dfs(area,visited,i-1,j);
        }
        if(area[i+1][j] == 1 && visited[i+1][j] == false) {
            // 下
            dfs(area,visited,i+1,j);
        }
        if(area[i][j-1] == 1 && visited[i][j-1] == false) {
            // 左
            dfs(area,visited,i,j-1);
        }
        if(area[i][j+1] == 1 && visited[i][j+1] == false) {
            // 右
            dfs(area,visited,i,j+1);
        }
    }
}
